//给你一个下标从 0 开始，大小为 m x n 的二进制矩阵 land ，其中 0 表示一单位的森林土地，1 表示一单位的农场土地。 
//
// 为了让农场保持有序，农场土地之间以矩形的 农场组 的形式存在。每一个农场组都 仅 包含农场土地。且题目保证不会有两个农场组相邻，也就是说一个农场组中的任何
//一块土地都 不会 与另一个农场组的任何一块土地在四个方向上相邻。 
//
// land 可以用坐标系统表示，其中 land 左上角坐标为 (0, 0) ，右下角坐标为 (m-1, n-1) 。请你找到所有 农场组 最左上角和最右下角
//的坐标。一个左上角坐标为 (r1, c1) 且右下角坐标为 (r2, c2) 的 农场组 用长度为 4 的数组 [r1, c1, r2, c2] 表示。 
//
// 请你返回一个二维数组，它包含若干个长度为 4 的子数组，每个子数组表示 land 中的一个 农场组 。如果没有任何农场组，请你返回一个空数组。可以以 任意
//顺序 返回所有农场组。 
//
// 示例 1： 
//
// 
//
// 输入：land = [[1,0,0],[0,1,1],[0,1,1]]
//输出：[[0,0,0,0],[1,1,2,2]]
//解释：
//第一个农场组的左上角为 land[0][0] ，右下角为 land[0][0] 。
//第二个农场组的左上角为 land[1][1] ，右下角为 land[2][2] 。
// 
//
// 示例 2： 
//
// 
//
// 输入：land = [[1,1],[1,1]]
//输出：[[0,0,1,1]]
//解释：
//第一个农场组左上角为 land[0][0] ，右下角为 land[1][1] 。
// 
//
// 示例 3： 
//
// 
//
// 输入：land = [[0]]
//输出：[]
//解释：
//没有任何农场组。
// 
//
// 
//
// 提示： 
//
// 
// m == land.length 
// n == land[i].length 
// 1 <= m, n <= 300 
// land 只包含 0 和 1 。 
// 农场组都是 矩形 的形状。 
// 
// Related Topics 深度优先搜索 广度优先搜索 数组 矩阵 
// 👍 6 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class FindAllGroupsOfFarmland {
    public static void main(String[] args) {
        Solution solution = new FindAllGroupsOfFarmland().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 使用dfs，比直接遍历矩阵更慢
         */
        int row,col;
        public int[][] findFarmland1(int[][] land) {
            List<int[]> res = new ArrayList<>();
            row = land.length;
            if (row == 0) return new int[0][0];
            col = land[0].length;
            if (col == 0) return new int[0][0];
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (land[i][j] == 1){ // 找到入口
                        int[] temp = new int[4];
                        temp[0] = i;
                        temp[1] = j;
                        dfs(i, j, land, temp);
                        res.add(temp);
                    }
                }
            }
            return res.toArray(new int[0][]);
        }

        public void dfs(int x, int y, int[][] land, int[] res){
            if (x >= row || y >= col || land[x][y] != 1) return;
            land[x][y] = 0;
            dfs(x + 1, y, land, res);
            dfs(x, y + 1, land, res);
            // 因为是右下递归，两边都不回溯回来后说明到右下角了，且只能赋值一次
            if (res[2] == 0 && res[3] == 0){
                res[2] = x;
                res[3] = y;
            }
        }

        /**
         * 因为矩阵非常工整，直接遍历反而更快
         */
        public int[][] findFarmland(int[][] land) {
            List<int[]> res = new ArrayList<>();
            row = land.length;
            if (row == 0) return new int[0][0];
            col = land[0].length;
            if (col == 0) return new int[0][0];
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (land[i][j] == 1){ // 找到入口
                        int[] temp = new int[4];
                        temp[0] = i;
                        temp[1] = j;
                        int k = i;
                        while (k < row && land[k][j] == 1) k++;
                        k--;
                        int l = j;
                        while (l < col && land[k][l] == 1) l++;
                        l--;
                        temp[2] = k;
                        temp[3] = l;
                        res.add(temp);
                        for (int m = i; m <= k ; m++) {
                            for (int n = j; n <= l; n++) {
                                land[m][n] = 0;
                            }
                        }
                    }
                }
            }
            return res.toArray(new int[0][]);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}





































